Partition list¶
Time: O(N); Space: O(1); medium
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example 1:
Input: head = {ListNode} None, x = 0
Output: {ListNode} None
Explanation:
The empty list Satisfy the conditions by itself.
Example 2:
Input: head = {ListNode} 1->4->3->2->5->2->None, x = 3
Output: {ListNode} 1->2->2->4->3->5->None
Explanation:
keep the original relative order of the nodes in each of the two partitions.
[7]:
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
def __repr__(self):
if self:
return "{} -> {}".format(self.val, repr(self.next))
Solution¶
The problem wants us to reform the linked list structure, such that the elements lesser that a certain value x, come before the elements greater or equal to x. This essentially means in this reformed list, there would be a point in the linked list before which all the elements would be smaller than x and after which all the elements would be greater or equal to x. Let’s call this point as the JOINT.
Reverse engineering the question tells us that if we break the reformed list at the JOINT, we will get two smaller linked lists, one with lesser elements and the other with elements greater or equal to x. In the solution, our main aim is to create these two linked lists and join them.
1: Two Pointer Approach Intuition
We can take two pointers before and after to keep track of the two linked lists as described above. These two pointers could be used two create two separate lists and then these lists could be combined to form the desired reformed list.
Algorithm
Initialize two pointers before and after. In the implementation we have initialized these two with a dummy ListNode. This helps to reduce the number of conditional checks we would need otherwise. You can try an implementation where you don’t initialize with a dummy node and see it yourself!
Dummy Node Initialization
Iterate the original linked list, using the head pointer.
If the node’s value pointed by head is lesser than x, the node should be part of the before list. So we move it to before list.
Else, the node should be part of after list. So we move it to after list.
https://leetcode.com/problems/partition-list/Figures/86/86_Partition_List_4.png
Once we are done with all the nodes in the original linked list, we would have two list before and after. The original list nodes are either part of before list or after list, depending on its value.
Note:
Since we traverse the original linked list from left to right, at no point would the order of nodes change relatively in the two lists. Another important thing to note here is that we show the original linked list intact in the above diagrams. However, in the implementation, we remove the nodes from the original linked list and attach them in the before or after list. We don’t utilize any additional space. We simply move the nodes from the original list around.
Now, these two lists before and after can be combined to form the reformed list.
We did a dummy node initialization at the start to make implementation easier, you don’t want that to be part of the returned list, hence just move ahead one node in both the lists while combining the two list. Since both before and after have an extra node at the front.
[8]:
class Solution1(object):
"""
Time: O(N)
Space: O(1)
"""
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
# before and after are the two pointers used to create two list
# before_head and after_head are used to save the heads of the two lists.
# All of these are initialized with the DUMMY nodes created.
before = before_head = ListNode(0)
after = after_head = ListNode(0)
while head:
# If the original list node is lesser than the given x,
# assign it to the before list.
if head.val < x:
before.next = head
before = before.next
else:
# If the original list node is greater or equal to the given x,
# assign it to the after list.
after.next = head
after = after.next
# move ahead in the original list
head = head.next
# Last node of "after" list would also be ending node of the reformed list
after.next = None
# Once all the nodes are correctly assigned to the two lists,
# combine them to form a single list which would be returned.
before.next = after_head.next
return before_head.next
[9]:
s = Solution1()
head = None
x = 0
res = s.partition(head, x)
assert res == None
head = ListNode(1)
head.next = ListNode(4)
head.next.next = ListNode(3)
head.next.next.next = ListNode(2)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = ListNode(2)
x = 3
res = s.partition(head, x)
assert res.val == 1
assert res.next.val == 2
assert res.next.next.val == 2
assert res.next.next.next.val == 4
assert res.next.next.next.next.val == 3
assert res.next.next.next.next.next.val == 5